package LearnAlgorithm.d_标准查找算法and标准排序算法;

import java.util.Arrays;

public class e2字符串匹配SuffixArrayNotStaticPlus倍增法 {
	public static void main(String[] args) {
		String mother = "ABABABABB";
        String child = "BABB";
        new e2字符串匹配SuffixArrayNotStaticPlus倍增法().suffixArrayMatch(mother, child);
	}
	
	/**
	 * O(N*logN*logN + N*logM)
	 * @param mother
	 * @param child
	 */
	public void suffixArrayMatch(String mother, String child) {
		Suff[] suffixArray = makeSuffixArray(mother);//O(N*logN*logN)
		int l = 0;
		int r = mother.length() - 1;
		//O(NlogM)
		while (r >= l) {//开始二分查找；必须>=，是为了保证索引1和最后的索引，这两个元素也能参与比较
			int mid = l + ((r - l) >>> 1);
			int compareResult = 0;
			String suffMid = suffixArray[mid].getString();
			if (suffMid.length() >= child.length()) {
				compareResult = suffMid.substring(0, child.length()).compareTo(child);
			} else {
				//为什么suffMid比child长度小还要比呢？它俩肯定是不相同的啊。
            	//是因为二分查找；注意这是在查找过程中；我们知道肯定不相同，我们的目的是利用二分查找特性进行下一次查找。
				compareResult = suffMid.compareTo(child);
			}
			if (compareResult == 0) {//判断找没找到
				System.out.println("index:" + suffixArray[mid].getIndex());
				return;
			} else if (compareResult < 0) {
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		System.out.println("没找到,输出所有的后缀数组：");
		printSuffixArray(suffixArray);
	}
	
	
	/**
	 * O(N*logN*logN)
	 * 倍增法优化
	 * suffixArray[i].getIndex = k
	 * 表示在后缀数组suffixArray中，排名是i(索引)的“后缀”，是从原串的第k索引开始的
	 * @param string
	 * @return
	 */
	public Suff[] makeSuffixArray(String string) {
		int length = string.length();
		int[] rk = new int[length];
		Suff[] suffixArray = new Suff[length];
		for (int k = 1; k <= length; k *= 2) {
			for (int i = 0; i < length; i++) {
				suffixArray[i] = new Suff(string.substring(i, i + k > length ? length : i + k), i);
				//substring(i, i + k > length ? length : i + k)
				/*
				我们假设length非常大，i+k在前面充足范围内不会打过length
				substring截取的索引范围是[i,i+k-1];
				倍增出来的新元素的首个索引是i+k/2;
				下面我们来举例(默认i=0)：
				k=1,i=0特殊，使用默认Arrays.sort；
				
				k=2,i=0
					存入suffixArray的字符片段的索引范围[0,1]
					i+k = 0+2 = 2
					i+k-1 = 0+2-1 = 1
					i+k/2 = 0+2/2 = 1
					上一次rk[]中存储的是长度为1的
					X		Y		NULL
					0		1		2
					i       i+k-1	i+k
							i+k/2
					'1'		'1'
							
				k=4,i=0
					存入suffixArray的字符片段的索引范围[0,3]
					i+k = 0+4 = 4
					i+k-1 = 0+4-1 = 3
					i+k/2 = 0+4/2 = 2
					上一次rk[]中存储的是长度为2的
					X		Y		A		B		NULL
					0		1		2		3		4
					i       		i+k/2	i+k-1	i+k
					'	2	'		'	2	'
					
					
				k=8,i=0
					存入suffixArray的字符片段的索引范围[0,7]
					i+k = 0+8 = 8
					i+k-1 = 0+8-1 = 7
					i+k/2 = 0+8/2 = 4
					上一次rk[]中存储的是长度为4的
					X		Y		A		B		C		D		E		F		NULL
					0		1		2		3		4		5		6		7		8
					i       						i+k/2					i+k-1	i+k
					'			4			'		'			4			'	
				 */
			}
			if (k == 1) {
				Arrays.sort(suffixArray);
			} else {
				final int kk = k;
				//上面那一大堆注释，我想表达的意思是
				//倍增法不会有排序遗漏和对比错误
				//将来的我不用杞人忧天
				Arrays.sort(suffixArray, (o1, o2) -> {
					//o1是this,是新元素；o2是other,是旧元素
					//这是一个匿名内部类，作为了排序规则；执行一次排序规则需要O(1)；但是排序一个数组就需要N个O(1)
					int x = ((Suff) o1).getIndex();
					int y = ((Suff) o2).getIndex();
					if (rk[x] == rk[y]) {
						try {
							//考虑到后面的元素在倍增时，不够长；
							//第一种不够长：i.....i+k/2....(没到i+k-1)
							//		这种不够长是能够走try的return的；想弄清楚的话，自己就多注意x,y到底是什么，x,y就是上面for循环中的i
							//第二种不够长：i.....(没到i+k/2)
							//		这种不够长需要走catch中的return；因为i+kk/2会索引越界
							return rk[x + kk / 2] - rk[y + kk / 2];
						} catch (Exception e) {
							//就在这里处理第二种不够长的“索引越界的情况”
							return o1.getString().length() - o2.getString().length();
						}
					} else {
						return rk[x] - rk[y];
					}
				});
			}
			//在排序之后，需要给排完序的suffixArray生成rk[]
			//因为suffixArray[i].getString()是可能相同的，所以这样的情况的两个suffixArray元素需要一样的rk[]值
			//下面的操作就做到了这一点
			int r = 0;//初始化rk[]值为0
			rk[suffixArray[0].getIndex()] = r;//初始化suffixArray首元素rk[]值；因为已经排序了，所以suffixArray第1个元素的rk[]值 = 0
			for (int i = 1; i < length; i++) {//遍历排完序的suffixArray
				if (suffixArray[i].compareTo(suffixArray[i - 1]) == 0) {//getString()相同
					rk[suffixArray[i].getIndex()] = r;//赋值一样的rk[]值
				} else {
					rk[suffixArray[i].getIndex()] = ++r;//不同；因为是排好序的suffixArray，所以直接把r++；不会产生错误的！
				}
			}
		}
		return suffixArray;
	}
	
	/**
	 * 打印Suff[]
	 * @param arr
	 */
	public void printSuffixArray(Suff[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
	}
	
	/**
	 * 自定义包含string,index的对象
	 * 并且实现比较方法
	 * @author wuqiu
	 *
	 */
	public class Suff implements Comparable<Suff> {
		private String string = null;
		private int index = 0;
		public Suff() {};
		public Suff(String string, int index) {
			this.string = string;
			this.index = index;
		}
		public void setString(String string) {
			this.string = string;
		}
		public String getString() {
			return this.string;
		}
		public void setIndex(int index) {
			this.index = index;
		}
		public int getIndex() {
			return this.index;
		}
		/*
		this是新元素，other是老元素
		this.string.compareTo(other.string)会返回一个int A
		Suff类的compareTo会返回一个int,实际上就是把A返回
		在使用了自然排序的集合中添加Suff类对象
		这些对象的顺序是根据A决定的
		A = 0，在有些集合中，新元素(this)就不会加入
		A > 0，this在other后面加入
		A < 0，this在other前面加入
		 */
		@Override
		public int compareTo(Suff other) {
			return this.string.compareTo(other.string);
		}	
		@Override
        public String toString() {
            return "Suff {" +
                    "string='" + string + '\'' +
                    ", index=" + index +
                    '}';
        }
	}
}
